package com.wzq.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution39 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> rstList = new ArrayList<List<Integer>>();

        Arrays.sort(candidates);

        foo(candidates,0,target,0,new ArrayList<Integer>(),rstList);
        return rstList;
    }


    public static void foo(int[] arr,int i,int target,int sum,List<Integer> sList,List<List<Integer>> rstList){

        if(target == sum){
            rstList.add(sList);
        }else{

            while(i<arr.length && sum + arr[i] <= target){
                List<Integer> newList = new ArrayList<Integer>(sList);
                newList.add(arr[i]);
                foo(arr,i,target,sum+arr[i],newList,rstList);
                i++;
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{2,3,5,4,7},7));
    }
}